Definition

Let AA be an algorithm that is a naïve PAC learner for functions 𝒳→𝒴\mathcal{X} \to \mathcal{Y}, for some sets 𝒳,𝒴\mathcal{X}, \mathcal{Y}. The sample complexity of AA is a function m:(0,1)2→ℕm: (0,1)^2 \to \mathbb{N} such that for every ε,δ∈(0,1)\varepsilon, \delta \in (0,1), the number m(ε,δ)m(\varepsilon, \delta) is the minimal sample size for which AA satisfies the requirement of naïve PAC learning,

ℙS∼(𝒟,f)m[L𝒟,f(h)≤ε]≥1−δ\mathbb{P}_{S \sim (\mathcal{D},f)^m} [L_{\mathcal{D},f}(h) \leq \varepsilon] \geq 1 - \delta

References

  1. J. Shafer, Class Lecture, Topic: "Unit 2: Probably Approximately Correct: A Probabilistic Definition of Learning." CS 294-220, UC Berkeley, Spring 2021. https://piazza.com/class_profile/get_resource/khs64r6r5yn154/kkeojz4edrt27